package com.xiaohe66.demo.arithmetic.leetcode.bit;

/**
 * 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 * <p>
 * 示例 1：
 * 输入：00000000000000000000000000001011
 * 输出：3
 * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 * <p>
 * 示例 2：
 * 输入：00000000000000000000000010000000
 * 输出：1
 * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
 * <p>
 * 示例 3：
 * 输入：11111111111111111111111111111101
 * 输出：31
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 * <p>
 * 提示：
 * 输入必须是长度为 32 的 二进制串 。
 * 注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/
 * <p>
 * 通过次数149,768提交次数203,227
 *
 * @author xiaohe
 * @time 2021.06.23 10:08
 * @see T191位1的个数
 */
public class T剑指Offer15二进制中1的个数 {

    /**
     * 官方题解
     * 核心思想：将最后一位的 1 变成 0
     * n & (n - 1)
     */
    public int hammingWeight(int n) {

        int ret = 0;
        while (n != 0) {

            /*
                核心思想：将最后一位的 1 变成 0
                101 & 000 = 100
                110 & 001 = 100
                100 & 001 = 000
             */
            n = n & (n - 1);
            ret++;
        }
        return ret;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了96.63%的用户
     * 内存消耗：35.5 MB, 在所有 Java 提交中击败了18.40%的用户
     */
    public int hammingWeight2(int n) {

        // 当值为负数时，接位取反转成正数来处理
        int tmp = n < 0 ? ~n : n;

        int ret = 0;
        while (tmp != 0) {
            ret += tmp & 1;
            // 如果使用无符号右移，就可以不用将负数转成正数了！！！！！
            tmp = tmp >> 1;
        }

        return n < 0 ? (32 - ret) : ret;
    }
}
